package com.zpself.module.算法练习.二叉树;

import java.util.ArrayList;

/**
 * @author By ZengPeng
 * @Description
 * @date in  2021/2/5 14:08
 * @Modified By
 */
public class 力扣_501_二叉搜索树中的众数 {

    public static void main(String[] args) {

        System.out.println(new 力扣_501_二叉搜索树中的众数().findMode(TreeNode.initRoot()));
    }
    //先序遍历 ，当前相同的个数max, 当前相同数字个数 currentNumber ，当前数
    int preVal = 0, curTimes = 0, maxTimes = 0;
    ArrayList<Integer> list = new ArrayList<>();
    public  int[] findMode(TreeNode root) {
        if(root==null)
            return new int[]{};
        //** int[] 位图不行啊，不知初始数组大小

        int max =0;
       traverse(root);

        //转换list为数组
        int[] data = new int[list.size()];
        for (int i=0;i<list.size() ; i++) {
            data[i] = list.get(i);
        }
        return data;
    }

     public  void traverse(TreeNode root) {
         if(root.left!=null)
             traverse(root.left);
         //判断当前值与上一个值的关系, 更新 curTimes 和 preVal
         if(preVal == root.val){
             curTimes++;
         }else{
             preVal = root.val;
             curTimes = 1;
         }
         //判断当前数量与最大数量的关系, 更新 list 和 maxTimes
         if(curTimes == maxTimes){
             list.add(root.val);
         }else if(curTimes > maxTimes){
             list.clear();
             list.add(root.val);
             maxTimes = curTimes;
         }
         if(root.right!=null)
             traverse(root.right);
     }
}
